package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

/**
 * @author zhangsan
 * @date 2021/4/9 15:22
 */
public class M0404 {

    // https://leetcode-cn.com/problems/check-balance-lcci/
    public static boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    private static Info process(TreeNode root) {
        if(root == null) return new Info(0, true);
        Info li = process(root.left);
        Info ri = process(root.right);
        int height = Math.max(li.height, ri.height) + 1;
        boolean isBalanced = li.isBalanced && ri.isBalanced && Math.abs(li.height - ri.height) < 2;
        return new Info(height, isBalanced);
    }

    private static class Info {
        int height;
        boolean isBalanced;
        public Info(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }


    // for test
    public static void main(String[] args) {
        Integer[] treeInfo = {
                3,9,20,null,null,15,7
        };
        TreeNode root = TreeUtil.generateTreeByArr(treeInfo);
        System.out.println(isBalanced(root));
    }

}
